// https://www.lintcode.com/problem/number-of-islands-ii/description

// /**
//  * Definition for a point.
//  * struct Point {
//  *     int x;
//  *     int y;
//  *     Point() : x(0), y(0) {}
//  *     Point(int a, int b) : x(a), y(b) {}
//  * };
//  */
// class UnionFind
// {
//     public:
//     map<int, int> father; //用map很慢
//     int cnt = 0;
    
//     // UnionFind(n, vector<Point> operators)
//     UnionFind()
//     {
//     }
    
//     void insert(int n)
//     {
// // 3
// // 3
// // [[0,0],[0,1],[2,2],[2,2]]
// // Output
// // [1,1,2,3]
// // Expected
// // [1,1,2,2]
//         if (!notSea(n))
//         {
//             father[n] = n;
//             cnt++;
//         }
//     }
    
//     int find(int i)
//     {
//         int x = i;
//         while (father[i] != i)
//         {
//             i = father[i];
//         }
//         while (x != i)
//         {
//             int tmp = father[x];
//             father[x] = i;
//             // x = father[x];
//             x = tmp;
//         }
//         return i;
//     }
    
//     bool notSea(int n)
//     {
//         return father.find(n) != father.end();
//     }
    
//     void connect(int a, int b)
//     {
//         int fa = find(a);
//         int fb = find(b);
//         if (fa != fb)
//         {
//             // father[a] = b; !!!
//             father[fa] = fb;
//             cnt--;
//         }
//     }
    
//     int get()
//     {
//         return cnt;
//     }
// };

// class Solution {
// public:
//     /**
//      * @param n: An integer
//      * @param m: An integer
//      * @param operators: an array of point
//      * @return: an integer array
//      */
//     vector<int> numIslands2(int n, int m, vector<Point> &operators) {
//         UnionFind uf;
//         int di[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
//         vector<int> res;
//         for (Point p: operators)
//         {
//             // int node = p.x * n + p.y;
//             int node = p.x * m + p.y; //注意是m不是n

//             uf.insert(node);
//             cout << p.x << " " << p.y << endl;
//             cout << uf.get() << endl;
//             for (int i = 0; i < 4; ++i)
//             {
//                 // if (p.x + di[i][0] >= 0 && p.x + di[i][0] < n && 
//                 //     p.y + di[i][1] > 0 && p.y + di[i][1] < m)
//                 // int newNode = (p.x + di[i][0]) * n + p.y + di[i][1];
//                 int newNode = (p.x + di[i][0]) * m + p.y + di[i][1];
//                 if (p.x + di[i][0] >= 0 && p.x + di[i][0] < n && 
//                     p.y + di[i][1] >= 0 && p.y + di[i][1] < m && uf.notSea(newNode))
//                 {
//                     uf.connect(newNode, node);
//                 }
//             }
//             res.push_back(uf.get());
//         }
//         return res;
//     }
// };



/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class UnionFind
{
    public:
    int* father;
    int cnt = 0;
    
    // UnionFind(n, vector<Point> operators)
    UnionFind(int n)
    {
        father = new int[n];
        for (int i = 0; i < n; ++i)
        {
            father[i] = -1;
        }
    }
    
    void insert(int n)
    {
// 3
// 3
// [[0,0],[0,1],[2,2],[2,2]]
// Output
// [1,1,2,3]
// Expected
// [1,1,2,2]
        if (!notSea(n))
        {
            father[n] = n;
            cnt++;
        }
    }
    
    int find(int i)
    {
        int x = i;
        while (father[i] != i)
        {
            i = father[i];
        }
        while (x != i)
        {
            int tmp = father[x];
            father[x] = i;
            // x = father[x];
            x = tmp;
        }
        return i;
    }
    
    bool notSea(int n)
    {
        // return father.find(n) != father.end();
        return father[n] != -1;
    }
    
    void connect(int a, int b)
    {
        int fa = find(a);
        int fb = find(b);
        if (fa != fb)
        {
            // father[a] = b; !!!
            father[fa] = fb;
            cnt--;
        }
    }
    
    int get()
    {
        return cnt;
    }
};


// 也可以并查集不写成类，更快一些
class Solution {
public:
    /**
     * @param n: An integer
     * @param m: An integer
     * @param operators: an array of point
     * @return: an integer array
     */
    vector<int> numIslands2(int n, int m, vector<Point> &operators) {
        UnionFind uf(n * m);
        int di[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        vector<int> res;
        for (Point p: operators)
        {
            // int node = p.x * n + p.y;
            int node = p.x * m + p.y; //注意是m不是n

            uf.insert(node);
            for (int i = 0; i < 4; ++i)
            {
                // if (p.x + di[i][0] >= 0 && p.x + di[i][0] < n && 
                //     p.y + di[i][1] > 0 && p.y + di[i][1] < m)
                // int newNode = (p.x + di[i][0]) * n + p.y + di[i][1];
                int newNode = (p.x + di[i][0]) * m + p.y + di[i][1];
                if (p.x + di[i][0] >= 0 && p.x + di[i][0] < n && 
                    p.y + di[i][1] >= 0 && p.y + di[i][1] < m && uf.notSea(newNode))
                {
                    uf.connect(newNode, node);
                }
            }
            res.push_back(uf.get());
        }
        return res;
    }
};